/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025/6/5
 * Time: 21:19
 */

public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode slow = head,fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode first = head,second = slow.next;
        slow.next = null;
        first = sortList(first);
        second = sortList(second);
        return mergeTwoLists(first,second);
    }
    public ListNode mergeTwoLists(ListNode headA, ListNode headB) {
        if(headA == null && headB == null) return null;
        if(headA == null && headB != null) return headB;
        if(headA != null && headB == null) return headA;
        ListNode newHead = new ListNode(-1);
        ListNode temp = newHead;
        while(headA != null && headB != null){
            if(headA.val >= headB.val){
                temp.next = headB;
                headB = headB.next;
            }else{
                temp.next = headA;
                headA = headA.next;
            }
            temp = temp.next;
        }
        while(headA != null){
            temp.next = headA;
            headA = headA.next;
            temp = temp.next;
        }
        while(headB != null){
            temp.next = headB;
            headB = headB.next;
            temp = temp.next;
        }
        return newHead.next;
    }
}